package leetcode.weekly.week311;

import java.util.HashMap;
import java.util.Map;


//Solution4Test
public class Solution4 {
	Node root;

	public int[] sumPrefixScores(String[] words) {
		root = new Node();
		for (String word : words) {
			this.insert(word);
		}
		int[] ans = new int[words.length];
		int j = 0;
		for (String word : words) {
			ans[j++] = this.search(word);
		}
		return ans;
	}

	private class Node {
		Node[] c = new Node[26];
		boolean end;
		int cnt = 0;
	}

	public void insert(String word) {
		Node node = root;
		for (char c : word.toCharArray()) {
			int idx = c - 'a';
			if (node.c[idx] == null)
				node.c[idx] = new Node();
			node.c[idx].cnt++;
			node = node.c[idx];
		}
		node.end = true;
	}

	public int search(String word) {
		Node node = root;
		int ans = 0;
		for (char c : word.toCharArray()) {
			int idx = c - 'a';
			ans += node.c[idx].cnt;
			node = node.c[idx];
		}
		return ans;
	}

}
